package com.note.feng.leetcode.algorithms.easy.eleven;

import java.util.HashMap;
import java.util.Map;

public class ThousandHundredThirtySeven {
    /**
     * 1137 第 N 个泰波那契数
     * 泰波那契序列 Tn 定义如下： 
     *
     * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
     *
     * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
     *
     * 示例 1：
     *
     * 输入：n = 4
     * 输出：4
     * 解释：
     * T_3 = 0 + 1 + 1 = 2
     * T_4 = 1 + 1 + 2 = 4
     * 示例 2：
     *
     * 输入：n = 25
     * 输出：1389537
     *
     * 提示：
     *
     * 0 <= n <= 37
     * 答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/n-th-tribonacci-number
     */
    /**
     * 解法：递归 + 缓存
     * 只是递归不加缓存，会超时
     * 用 map 缓存计算过的值，不再重复计算
     * @param n
     * @return
     */
    Map<Integer, Integer> map = new HashMap<>();
    public int tribonacci(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 1;
        }
        if(map.containsKey(n)){
            return map.get(n);
        }
        map.put(n, tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3));
        return map.get(n);
    }

    /**
     * 解法二：动态规划 滑动窗口
     * 每一个数，都和它前面的3个数有关系，可以动态计算出来
     * @param n
     * @return
     */
    public int tribonacci2(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 1;
        }
        int res = 0,p = 0,q = 1, r = 1;
        for (int i = 3; i <= n; i++) {
            res = p + q + r;
            p = q;
            q = r;
            r = res;
        }
        return res;
    }
}
